Surprise Killer Problem

Problem
Code

Today was rough.

Part 1 was kicking my ass so bad, I had to switch to a completely different method of calculating intersections. At first I took a formula from Wikipedia, but it kinda just... didn't work? I'm not clear what the mistake was, and other people were struggling with the exact same thing.

Eventually, I ended up adapting some random intersection code I found. That took care of part 1.

Part 2 was what we in the biz call "fucking brutal". After I solved it, I looked at Reddit—plenty of people apparently fed the whole thing as a set of equations into a solver like z3 or Mathematica. Thankfully I accidentally stumbled upon a reasonable solution.

Core idea is this: We can treat each axis separately for finding the velocity of our wonder rock. And, something that part 1 is meant to lead you towards, is that some hailstones have the same velocity along certain axis. Meaning that they'll maintain the same distance.

So, if we have two hailstones that maintain a constant X distance, we can use it to constrain the possible X velocities of our magic rock, because we assume all the speeds are integers.

type P = ([f64; 3], [f64; 3]);
fn velocity_for_axis(lines: &[(P, P)], axis: usize) -> Option<f64> {
    let mut candidates = HashSet::new();
    for (i, &(p1, v1)) in lines.iter().enumerate() {
        for &(p2, v2) in lines[(i + 1)..].iter() {
            if v1[axis] == v2[axis] && v1[axis].abs() > 128.0 {
                let mut set = HashSet::new();
                for candidate in -400..=400 {
                    let candidate = candidate as f64;
                    if candidate == v1[axis] {
                        continue;
                    }
                    if (p2[axis] - p1[axis]) % (candidate - v1[axis]).abs() < f64::EPSILON {
                        set.insert(candidate as i64);
                    }
                }

                if candidates.is_empty() {
                    candidates.extend(set);
                } else {
                    candidates.retain(|v| set.contains(v));
                }
            }
        }
    }
    (candidates.len() == 1).then(|| candidates.into_iter().next().unwrap() as f64)
}

Here I find any pair that has the same velocity along the chosen axis, but is at least 128 units apart (arbitrary condition that just speeds up calculations by skipping some redundant work, you can skip it). Then, I find all integer velocities from -400 to 400 (again, arbitrary bounds... if it hadn't worked, I woulda just increased this number) that are able to hit both of them.

The rock is able to hit both of them if its speed relative to the pair neatly divides their distances. For example if the rock moves at speed 10, and the hailstones at speed 3, the hailstones would have to be 7, 14, 21, 28... apart in order for the rock to be able to hit both of them.

So, we do that for each axis independently, and then have the actual velocity of our rock.

With our velocity, for any given hailstone, we can build a line containing all possible starting positions that allow us to hit that hailstone. Do that twice, for two arbitrary hailstones. Now we have two lines of possible starting positions. Intersect those two lines to find the true starting position.

let ([x1, y1, z1], [vx1, vy1, vz1]) = lines[0];
let ([x2, y2, _], [vx2, vy2, _]) = lines[1];

let a1 = (vy1 - vy) / (vx1 - vx);
let b1 = y1 - a1 * x1;
let a2 = (vy2 - vy) / (vx2 - vx);
let b2 = y2 - a2 * x2;

let x = (b2 - b1) / (a1 - a2);
let y = a1 * x + b1;
let z = z1 + (vz1 - vz) * ((x - x1) / (vx1 - vx));

First of all, we ignore the Z coordinate, because we know that the lines intersect (otherwise there would be no solution!), and doing it in 2D is easier.

a and b are named after the constants in a line equation, y = ax + b. (a1, b1) and (a2, b2) each describe one of the possible-starting-position-lines described earlier. x is calculated from the intersection; y is then calculated from one of the two line equations we have; z is then calculated by finding out how much "time" has passed, and moving along the line that much.

Getting there was rough, but looking back I feel like the solution is pretty logical.